package com.org.gameloft.GLIDER.util.diff;

import java.util.ArrayList;

/**
 * Created by Claudiu-Florin FILIMON
 * Date: Aug 7, 2007
 * Time: 11:52:55 AM
 * Revision: 0
 */
public class DiffImpl implements Diff
{
    public Difference[] diff(Comparable[] s1, Comparable[] s2, DiffPoint[] points)
    {
        ArrayList diffs = new ArrayList(Math.max(s1.length, s2.length));

        for (int i = 0; i < points.length - 1; i++)
        {
            processDiff(diffs, s1, s2, points[i].line_left, points[i + 1].line_left, points[i].line_right, points[i + 1].line_right);
        }

        Difference[] d = new Difference[diffs.size()];
        for (int i = 0; i < diffs.size(); i++)
            d[i] = (Difference) diffs.get(i);

        return d;
    }

    private void processDiff(ArrayList diffs, Comparable[] s1, Comparable[] s2, int s1p1, int s1p2, int s2p1, int s2p2)
    {
        int m = s1p2 - s1p1;
        int n = s2p2 - s2p1;

        // opt[i][j] = length of LCS of x[i..M] and y[j..N]
        int[][] opt = new int[m + 1][n + 1];

        // compute length of LCS and all subproblems via dynamic programming
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >= 0; j--)
            {
                if (s1[i + s1p1].equals(s2[j + s2p1]))
                    opt[i][j] = opt[i + 1][j + 1] + 1;
                else
                    opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
            }
        }

        // recover LCS itself and print out non-matching lines to standard output
        int i = 0, j = 0;
        while (i < m && j < n)
        {
            if (s1[i + s1p1].equals(s2[j + s2p1]))
            {
                diffs.add(new Difference(Difference.EQUAL, i + s1p1, j + s2p1));
                i++;
                j++;
            }
            else
                if (opt[i + 1][j] >= opt[i][j + 1])
                {
                    diffs.add(new Difference(Difference.REMOVE, i + s1p1, j + s2p1));
                    i++;
                }
                else
                {
                    diffs.add(new Difference(Difference.INSERT, i + s1p1, j + s2p1));
                    j++;
                }
        }

        // dump out one remainder of one string if the other is exhausted
        while (i < m || j < n)
        {
            if (i == m)
            {
                diffs.add(new Difference(Difference.INSERT, i + s1p1, j + s2p1));
                j++;
            }
            else
                if (j == n)
                {
                    diffs.add(new Difference(Difference.REMOVE, i + s1p1, j + s2p1));
                    i++;
                }
        }
    }

//
//  code implementation from http://www.cs.princeton.edu/introcs/96optimization/Diff.java.html
//
//    public static void main(String[] args) {
//        int MAX = 10000;
//        String[] x = new String[MAX];   // lines in first file
//        String[] y = new String[MAX];   // lines in second file
//        int M = 0;                      // number of lines of first file
//        int N = 0;                      // number of lines of second file
//
//        // read in input from two files
//        In in0 = new In(args[0]);
//        In in1 = new In(args[1]);
//        String line;
//        while ((line = in0.readLine()) != null)
//            x[M++] = line;
//        while ((line = in1.readLine()) != null)
//            y[N++] = line;
//
//
//        // opt[i][j] = length of LCS of x[i..M] and y[j..N]
//        int[][] opt = new int[M+1][N+1];
//
//        // compute length of LCS and all subproblems via dynamic programming
//        for (int i = M-1; i >= 0; i--) {
//            for (int j = N-1; j >= 0; j--) {
//                if (x[i].equals(y[j]))
//                    opt[i][j] = opt[i+1][j+1] + 1;
//                else
//                    opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
//            }
//        }
//
//        // recover LCS itself and print out non-matching lines to standard output
//        int i = 0, j = 0;
//        while(i < M && j < N) {
//            if (x[i].equals(y[j])) {
//                i++;
//                j++;
//            }
//            else if (opt[i+1][j] >= opt[i][j+1]) System.out.println("< " + x[i++]);
//            else                                 System.out.println("> " + y[j++]);
//        }
//
//        // dump out one remainder of one string if the other is exhausted
//        while(i < M || j < N) {
//            if      (i == M) System.out.println("> " + y[j++]);
//            else if (j == N) System.out.println("< " + x[i++]);
//        }
//    }
}
